
public class SAP {
	
	private final Digraph mG;
	
	// constructor takes a digraph (not necessarily a DAG)
	public SAP(Digraph G)
	{
/*
		int[] numIncoming = new int[G.V()];
		int[] numOutgoing = new int[G.V()];
		for(int v = 0; v < G.V(); v++)
			for(int w: G.adj(v))
			{
				numOutgoing[v]++;
				numIncoming[w]++;
		 	}
			
		int numRoots = 0;
		for(int i = 0; i < G.V(); i++)
			if(numOutgoing[i] == 0 && numIncoming[i] > 0) {
				System.out.println("Root: " + i);
				numRoots++;
			}
		
		if(numRoots != 1)
			throw new java.lang.IllegalArgumentException();
	*/	
		mG = new Digraph(G);
	}
	
	private void checkBoundary(int x)
	{
		if(x < 0 || x >= mG.V())
			throw new java.lang.IndexOutOfBoundsException();
	}
	
	private int[] ancestorImpl(int v, int w)
	{
		checkBoundary(v);
		checkBoundary(w);
		
		BreadthFirstDirectedPaths bfsv = new BreadthFirstDirectedPaths(mG, v);
		BreadthFirstDirectedPaths bfsw = new BreadthFirstDirectedPaths(mG, w);

		int minArg     = -1;
		int minPathLen = -1;
		
		for(int i = 0, len = mG.V(); i < len; i++)
			if(bfsw.hasPathTo(i) && bfsv.hasPathTo(i)) {
				int pathLen = bfsw.distTo(i) + bfsv.distTo(i);
				if(minPathLen < 0 || pathLen < minPathLen) {
					minPathLen = pathLen;
					minArg     = i;
				}
			}
		
		return new int[]{ minPathLen, minArg };
	}

	// length of shortest ancestral path between v and w; -1 if no such path
	public int length(int v, int w)
	{
		return ancestorImpl(v, w)[0];
	}

	// a common ancestor of v and w that participates in a shortest ancestral path; -1 if no such path
	public int ancestor(int v, int w)
	{
		return ancestorImpl(v, w)[1];
	}

	private int[] ancestorImpl(Iterable<Integer> v, Iterable<Integer> w)
	{
		if(v == null || w == null)
			throw new java.lang.IllegalArgumentException();
		
		for(int i: v) checkBoundary(i);
		for(int i: w) checkBoundary(i);
		
		BreadthFirstDirectedPaths bfsv = new BreadthFirstDirectedPaths(mG, v);
		BreadthFirstDirectedPaths bfsw = new BreadthFirstDirectedPaths(mG, w);

		int minArg     = -1;
		int minPathLen = -1;
		
		for(int i = 0, len = mG.V(); i < len; i++)
			if(bfsw.hasPathTo(i) && bfsv.hasPathTo(i)) {
				int pathLen = bfsw.distTo(i) + bfsv.distTo(i);
				if(minPathLen < 0 || pathLen < minPathLen) {
					minPathLen = pathLen;
					minArg     = i;
				}
			}
		
		return new int[]{ minPathLen, minArg };
	}

	// length of shortest ancestral path between any vertex in v and any vertex in w; -1 if no such path
	public int length(Iterable<Integer> v, Iterable<Integer> w)
	{
		return ancestorImpl(v, w)[0];
	}

	// a common ancestor that participates in shortest ancestral path; -1 if no such path
	public int ancestor(Iterable<Integer> v, Iterable<Integer> w)
	{
		return ancestorImpl(v, w)[1];
	}

	// for unit testing of this class (such as the one below)
	public static void main(String[] args)
	{
	    In in = new In(args[0]);
	    Digraph G = new Digraph(in);
	    SAP sap = new SAP(G);
	    while (!StdIn.isEmpty()) {
	        int v = StdIn.readInt();
	        int w = StdIn.readInt();
	        int length   = sap.length(v, w);
	        int ancestor = sap.ancestor(v, w);
	        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
	    }
	}
}
